package com.acwing.partition9;

import java.io.*;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/12/1 12:19
 */
public class AC851spfa求最短路 {

    private static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            int x = Integer.parseInt(s[0]), y = Integer.parseInt(s[1]), z = Integer.parseInt(s[2]);
            edges[i][0] = x;
            edges[i][1] = y;
            edges[i][2] = z;
        }
        int ans = spfa(n, edges, 1, n);
        if (ans == INF) writer.write("impossible\n");
        else writer.write(ans + "\n");
        writer.flush();
    }

    private static int spfa(int n, int[][] edges, int start, int end) {
        int m = edges.length, index = 0;
        int[] head = new int[n + 1], element = new int[m], next = new int[m], weight = new int[m];
        int[] distance = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            head[i] = -1;
            distance[i] = INF;
        }
        distance[start] = 0;
        //建立邻接表
        for (int[] edge : edges) {
            element[index] = edge[1];
            next[index] = head[edge[0]];
            head[edge[0]] = index;
            weight[index++] = edge[2];
        }
        //记录结点是否在队列中，只有在队列中的结点才有更新的机会
        boolean[] inQueue = new boolean[n + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(start);
        inQueue[start] = true;
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            inQueue[u] = false;
            //更新u到其它点的距离
            for (int i = head[u]; i != -1; i = next[i]) {
                int v = element[i];
                if (distance[v] > distance[u] + weight[i]) {
                    distance[v] = distance[u] + weight[i];
                    if (inQueue[v]) continue;
                    queue.addLast(v);
                }
            }
        }
        return distance[end];
    }
}
